/**
 * Created with IntelliJ IDEA.
 * Description: 输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，
 *              子数组最小长度为1。求所有子数组的和的最大值。
 * User: 86187
 * Date: 2022-10-09
 * Time: 15:41
 */
public class Test {
    /**
     *  时间复杂度: O(n)  空间复杂度: O(n)
     */
    public static int FindGreatestSumOfSubArray(int[] array) {
        // 动归解决:
        // 1. f(i): 以i下标结尾的最大连续序列和,包含i下标元素.
        // 2. f(i) = Max(f(i-1)+array[i],array[i])
        // 3. f(0) = max = array[0]
        int length = array.length;
        if(length == 1) return array[0];

        //动归数组
        int[] dp = new int[length];

        dp[0] = array[0];
        int max = array[0];
        int i = 1;
        while(i < length) {
            dp[i] = Math.max(dp[i-1]+array[i],array[i]);
            if(dp[i] > max) max = dp[i];
            ++i;
        }

        return max;
    }

    /**
     * 优化后的动归:
     * 时间复杂度: O(n)  空间复杂度: O(1)
     */
    public static int FindGreatestSumOfSubArray2(int[] array) {
        int length = array.length;
        if(length == 1) return array[0];

        int total =  array[0];
        int max = array[0];
        int i = 1;
        while(i < length) {
            if(total > 0) {
                total += array[i++];
            } else {
                total = array[i++];
            }
            if(max < total) max = total;
        }
        return max;
    }
    public static void main(String[] args) {
        int[] array = {1,-2,3,10,-4,7,2,-5};

        System.out.println(FindGreatestSumOfSubArray(array)); // 18

        System.out.println(FindGreatestSumOfSubArray2(array)); // 18

    }
}
